The present invention is related to a scheme for addressing memory and more particularly to systems and method for using memory to implement multiple priority lists listing tasks to be performed.
Retransmitting data upon request is a well-known method for improving error performance in data communication systems where errors are detectable and a link from the receiver to the transmitter is available. Systems that provide this retransmission capability are often known as ARQ (Automatic Retransmission ReQuest) systems. For example, if a single request for retransmission may always be made and fulfilled, a channel having a bit error rate of 1×10−6 may have its effective bit error rate reduced to 1×10−12.
An ARQ system is described in the co-filed application entitled IMPROVED ARQ FOR POINT TO POINT LINKS. In the system described there, data communication between two ends of a point to point link is divided into codewords. The encoding schemes and decoding schemes employed by the link allow the receiver to determine whether a given codeword has been received in error. When the receiver detects that a codeword has been received in error, it may transmit a retransmission request to the transmitter via a reverse link. The transmitter may fulfill the retransmission request one or more times.
Communication of retransmission requests and actual retransmissions consumes link capacity that is therefore unavailable for first time transmissions of data. A representative ARQ system fixes the ratio between retransmission requests and codeword transmissions over a link. This representative ARQ system allows some programmability of the maximum percentage of link capacity usable for requested retransmissions and the number of consecutive codewords that may be used for retransmissions as opposed to new transmissions of data. This capacity is consumed on an “as-needed” basis; when there are no errors, no extra retransmission overhead is used.
When retransmissions are requested, it would be desirable to fulfill all recent pending requests at least n−1 times before fulfilling any pending request n times. In the other direction, it would be desirable to send n−1 retransmission requests in response to all recently received corrupted codewords before sending an nth retransmission request for any corrupted codeword. In this way, available link capacity for ARQ operation may be optimally shared among corrupted codewords.
A priority scheme that provides this desirable property is described in the co-filed application. Multiple priority lists are provided with the number of priority lists corresponding to the maximum permissible number of retransmissions. When a new request for retransmission is received, it causes creation of a corresponding entry on the highest priority list, the entry indicating which codeword is to be transmitted. When there is a retransmission opportunity, the oldest entry is removed from the highest priority non-empty list and the codeword that it identifies is retransmitted. This entry is then moved to the next highest priority list after a programmable delay. A similar priority list scheme is used to handle retransmission requests as opposed to the retransmissions themselves. It should be noted that the ARQ scheme described here is not admitted to be prior art to the present application.
It is desirable to provide as many priority lists as possible to maximize the number of possible retransmissions or retransmission requests when capacity is available so that the probability of correct transmission is maximized. It is also desirable to maximize the storage capacity available for each priority list as large as possible to maximize the number of pending retransmissions or retransmission requests that may be serviced before it is necessary to overwrite priority list memory. It is further desirable to include the priority list memory on the same integrated circuit to maximize speed and minimize size and cost. The desired integration and maximization of storage capacity are contradictory objectives. Maintaining multiple priority lists of sufficient length would require off-chip memory.